//
// 深度优先与广度优先搜索
// Created by 麻再挺 on 2021/12/16.
//

#ifndef DATA_STRUCTURE_C_SEARCH_GRAPH_H
#define DATA_STRUCTURE_C_SEARCH_GRAPH_H

#include <stdio.h>
#include <stdlib.h>
#include "graph_constant.h"
#include "./../constant.h"

// 设置全局数组，记录标记顶点是否被访问过
bool visited[MAX_VERTEX_NUM];

// 结点信息
typedef struct {
    // 对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    VRType adj;
    // 弧或边额外含有的信息指针
    InfoType *info;
} SArcCell, SAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 图结构
typedef struct {
    // 存储图中顶点数据
    VertexType vex[MAX_VERTEX_NUM];
    // 二维数组，记录顶点之间的关系
    SAdjMatrix arcs;
    // 记录图的顶点数和弧（边）数
    int vexNum, arcNum;
} SMGraph;

/**
 * 初始无向网-搜索图
 * @param g  图
 * @param vexNum 顶点数
 * @param arcNum 弧数
 * @param arr 弧数组
 */
void CreateSDN(SMGraph *g, int vexNum, int arcNum, int arr[]);

/**
 * 深度优先搜索
 */
void DFSTraverse(SMGraph g);

/**
 * 广度优先搜索
 * @param g 图
 */
void BFSTraverse(SMGraph g);

/**
 * 打印图
 * @param g 图
 */
void PrintSGraph(SMGraph g);

/**
 * 搜索元素
 * @param g 图
 * @param v 元素
 * @return
 */
int LocateSVex(SMGraph *g, int v);

/**
 * 打印图结点
 * @param g 图
 * @param v 值
 */
void visitVex(SMGraph g, int index);

/**
 * 查找图结点的第一条边
 * @param g 图
 * @param index 索引
 * @return
 */
int FirstAdjVex(SMGraph g, int index);

/**
 * 查找图结点的下一条边
 * @param g 图
 * @param index 索引
 * @param curInx 当前位置
 * @return
 */
int NextAjdVex(SMGraph g, int index, int curInx);



#endif //DATA_STRUCTURE_C_SEARCH_GRAPH_H
